package LinkedList;

public class _19_RemoveNthNodeFromEndofList {

    //use slow and fast node to minimize the circle's length
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int countFast = 1,countSlow = 1;
        ListNode slow = head,fast = head;
        while(fast.next!=null && fast.next.next!=null){
            fast = fast.next.next;
            slow =slow.next;
            countFast+=2;
            countSlow+=1;
        }
        if(fast.next!=null){
            countFast+=1;
        }
        if(countFast==1){
            return null;
        }
        if (countFast == n) {
            head = head.next;
        }
        if(countFast-n<countSlow){
            slow = head;
            countSlow = 1;
        }
        while(slow.next!=null){
            if (countSlow+1 == (countFast - n+1)) {
                slow.next = slow.next.next;
                break;
            }
            countSlow++;
            slow = slow.next;
        }
        return head;

    }
// think about the begin and the end nodes of the listnode
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        ListNode p = head;
        if(p.next==null && n==1){
            return null;
        }
        int num = 0;
        while (p != null) {
            num++;
            p = p.next;
        }
        if(num==n){
            head = head.next;
        }
        p = head;
        int count = 0;
        while (p.next != null) {
            count++;
            if(count+1==num-n+1){
                p.next = p.next.next;
                break;
            }
            p = p.next;
        }
        return head;
    }
}
